package bin_tree.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 使用层序遍历来判断是否是对称的树
 **/
public class Num101_2{
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            // 一次取出两个节点，这两个节点就是两颗子树的根节点
            TreeNode t1 = queue.poll();
            TreeNode t2 = queue.poll();
            if (t1 == null && t2 == null) {
                // 左右两棵树都是空树
                // 继续后面的判断
                continue;
            }
            if (t1 == null || t2 == null) {
                return false;
            }
            if (t1.val != t2.val) {
                return false;
            }
            // 左右两棵树都不为空且根节点的节点值是相同，继续判断t1.left和t2.right以及t1.right和t2.left
            queue.offer(t1.left);
            queue.offer(t2.right);
            // 再入队另一组元素
            queue.offer(t1.right);
            queue.offer(t2.left);
        }
        return true;
    }
}